package code;

import java.util.ArrayList;
import java.util.List;

public class Subsets {
	
	public int mergeSort(int l,int r,int[] array){
		if(l==r){
			return 0;
		}
		int mid=l+r>>1;
		int lcnt=mergeSort(l,mid,array);
		int rcnt=mergeSort(mid+1,r,array);
		int sum=lcnt+rcnt;
		int[] tmp=new int[r-l+1];
		int idx=0;
		int i,j;
		for(i=l,j=mid+1;i<=mid && j<=r;){
			if(array[i]>array[j]){
				sum++;
				tmp[idx++]=array[j];
				j++;
			}
			else{
				tmp[idx++]=array[i];
				i++;
			}
		}
		for(;i<=mid;i++)	tmp[idx++]=array[i];
		for(;j<=r;j++)	tmp[idx++]=array[j];
		for(i=0;i<r-l+1;i++)
			array[l+i]=tmp[i];
		return sum;
	}
	
	public List<List<Integer>> subsets(int[] S) {
		
		int n=S.length;
		List<List<Integer>> result=new ArrayList<List<Integer>>();
		if(n==0) return result;
		int i,j;
		mergeSort(0,n-1,S);
		int N=(1<<n);
		for(i=0;i<N;i++){
			List<Integer> list=new ArrayList<Integer>();
			for(j=0;j<n;j++){
				if(((1<<j)&i)!=0){
					list.add(S[j]);
				}
			}
			result.add(list);
		}
		for(i=0;i<result.size();i++){
			for(j=0;j<result.get(i).size();j++)
				System.out.print(result.get(i).get(j)+" ");
			System.out.println();
		}
        return result;
    }
	public static void main(String[] args){
		int[] S={1,2,3};
		new Subsets().subsets(S);
	}
}
